# -*- coding: utf-8 -*-

"""在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，
39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而Josephus 和他的朋友并不想遵从。请问，Josephus和他朋友在什么位置合适才能避免自杀？"""


from classic.linkedlist import SingleLinkedList

mans = SingleLinkedList(*range(1, 42))
guns = SingleLinkedList(1,2,3)

def generate_circle_link_list(ls):
    p = ls.head.next
    while True:
        if not p.next:
            break
        p = p.next
    p.next = ls.head.next

generate_circle_link_list(mans)
generate_circle_link_list(guns)

def suicide():
    pmp, pm, pg = mans.head, mans.head.next, guns.head.next
    print(pmp.data, pm.data, pg.data)
    while True:
        if mans.length == 2:
            break
        if pg.data == 3:
            print(pm.data, end=',')
            pmp.next = pm.next
            mans.length -= 1
            pm, pg = pm.next, pg.next
            mans.head = pm
        else:
            pmp, pm, pg = pmp.next, pm.next, pg.next

suicide()

print('')

print('...........')
print(mans.find(0))
print(mans.find(1))
